<!DOCTYPE html>
<html lang=zh>
<head>
    <meta charset="utf-8">
    
    <title>Alison&#39;s Space</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
    <meta property="og:type" content="website">
<meta property="og:title" content="Alison&#39;s Space">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="Alison&#39;s Space">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Alison&#39;s Space">
    

    

    

    <link rel="stylesheet" href="/libs/font-awesome/css/font-awesome.min.css">
    <link rel="stylesheet" href="/libs/open-sans/styles.css">
    <link rel="stylesheet" href="/libs/source-code-pro/styles.css">

    <link rel="stylesheet" href="/css/style.css">

    <script src="/libs/jquery/2.1.3/jquery.min.js"></script>
    
    
        <link rel="stylesheet" href="/libs/lightgallery/css/lightgallery.min.css">
    
    
        <link rel="stylesheet" href="/libs/justified-gallery/justifiedGallery.min.css">
    
    
        <script type="text/javascript">
(function(i,s,o,g,r,a,m) {i['GoogleAnalyticsObject']=r;i[r]=i[r]||function() {
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

ga('create', 'UA-102888086-1# enter the tracking ID for your Google Analytics', 'auto');
ga('send', 'pageview');

</script>
    
    
    


</head>

<body>
    <div id="container">
        <header id="header">
    <div id="header-main" class="header-inner">
        <div class="outer">
            <a href="/" id="logo">
                <i class="logo"></i>
                <span class="site-title">Alison&#39;s Space</span>
            </a>
            <nav id="main-nav">
                
                    <a class="main-nav-link" href="/.">Home</a>
                
                    <a class="main-nav-link" href="/archives">Archives</a>
                
                    <a class="main-nav-link" href="/categories">Categories</a>
                
                    <a class="main-nav-link" href="/tags">Tags</a>
                
                    <a class="main-nav-link" href="/about">About</a>
                
            </nav>
            
                
                <nav id="sub-nav">
                    <div class="profile" id="profile-nav">
                        <a id="profile-anchor" href="javascript:;">
                            <img class="avatar" src="/css/images/avatar.jpg" />
                            <i class="fa fa-caret-down"></i>
                        </a>
                    </div>
                </nav>
            
            <div id="search-form-wrap">

    <form class="search-form">
        <input type="text" class="ins-search-input search-form-input" placeholder="搜索" />
        <button type="submit" class="search-form-submit"></button>
    </form>
    <div class="ins-search">
    <div class="ins-search-mask"></div>
    <div class="ins-search-container">
        <div class="ins-input-wrapper">
            <input type="text" class="ins-search-input" placeholder="想要查找什么..." />
            <span class="ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
            UNTITLED: '(未命名)',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>
<script src="/js/insight.js"></script>

</div>
        </div>
    </div>
    <div id="main-nav-mobile" class="header-sub header-inner">
        <table class="menu outer">
            <tr>
                
                    <td><a class="main-nav-link" href="/.">Home</a></td>
                
                    <td><a class="main-nav-link" href="/archives">Archives</a></td>
                
                    <td><a class="main-nav-link" href="/categories">Categories</a></td>
                
                    <td><a class="main-nav-link" href="/tags">Tags</a></td>
                
                    <td><a class="main-nav-link" href="/about">About</a></td>
                
                <td>
                    
    <div class="search-form">
        <input type="text" class="ins-search-input search-form-input" placeholder="搜索" />
    </div>

                </td>
            </tr>
        </table>
    </div>
</header>

        <div class="outer">
            
                

<aside id="profile">
    <div class="inner profile-inner">
        <div class="base-info profile-block">
            <img id="avatar" src="/css/images/avatar.jpg" />
            <h2 id="name">Alison</h2>
            <h3 id="title">Java Programmer</h3>
            <span id="location"><i class="fa fa-map-marker"></i>Shanghai, China</span>
            <a id="follow" target="_blank" href="https://github.com/AlphaUMa/">关注我</a>
        </div>
        <div class="article-info profile-block">
            <div class="article-info-block">
                30
                <span>文章</span>
            </div>
            <div class="article-info-block">
                22
                <span>标签</span>
            </div>
        </div>
        
        <div class="profile-block social-links">
            <table>
                <tr>
                    
                    
                    <td>
                        <a href="https://github.com/AlphaUMa/" target="_blank" title="github" class=tooltip>
                            <i class="fa fa-github"></i>
                        </a>
                    </td>
                    
                </tr>
            </table>
        </div>
        
    </div>
</aside>

            
            <section id="main">
    <article id="post-alg_3" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/11/02/alg_3/">Ternary search（三元搜索）</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/11/02/alg_3/">
            <time datetime="2017-11-02T08:25:05.694Z" itemprop="datePublished">2017-11-02</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/算法和数据结构/">算法和数据结构</a>
    </div>

                        
                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h1 id="要点"><a href="#要点" class="headerlink" title="要点"></a>要点</h1><ul>
<li>用于单调函数求最值</li>
<li><p>有两个中间变量m1,m2</p>
<h1 id="逻辑"><a href="#逻辑" class="headerlink" title="逻辑"></a>逻辑</h1><p>Let a unimodal function <code>f(x)</code> on some interval <code>[l; r]</code>. Take any two points <code>m1</code> and <code>m2</code> in this segment: <code>l &lt; m1 &lt; m2 &lt; r</code>. Then there are three possibilities:</p>
</li>
<li><p>if <code>f(m1) &lt; f(m2)</code>, then the required maximum can not be located on the <code>left side - [l; m1]</code>. It means that the maximum further makes sense to look only in the interval <code>[m1;r]</code></p>
</li>
<li><p>if <code>f(m1) &gt; f(m2)</code>, that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the <code>right side - [m2; r]</code>, so go to the segment <code>[l; m2]</code></p>
</li>
<li><p>if <code>f(m1) = f(m2)</code>, then the search should be conducted in <code>[m1; m2]</code>, but this case can be attributed to any of the previous two (in order to simplify the code). Sooner or later the length of the segment will be a little less than a predetermined constant, and the process can be stopped.</p>
</li>
</ul>
<p>choice points <code>m1</code> and <code>m2</code>:</p>
<ul>
<li><p><code>m1 = l + (r-l)/3</code></p>
</li>
<li><p><code>m2 = r - (r-l)/3</code></p>
</li>
</ul>
<h1 id="Run-time-order"><a href="#Run-time-order" class="headerlink" title="Run time order"></a>Run time order</h1><p>$$T(n)=T(2n/3)+1=\theta (\log{n})$$</p>
<h1 id="Code"><a href="#Code" class="headerlink" title="Code"></a>Code</h1><h5 id="R-ecursive-algorithm"><a href="#R-ecursive-algorithm" class="headerlink" title="R ecursive algorithm"></a>R ecursive algorithm</h5><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div></pre></td><td class="code"><pre><div class="line">def ternarySearch(f, left, right, absolutePrecision):</div><div class="line">    &apos;&apos;&apos;</div><div class="line">    left and right are the current bounds; </div><div class="line">    the maximum is between them</div><div class="line">    &apos;&apos;&apos;</div><div class="line">    if abs(right - left) &lt; absolutePrecision:</div><div class="line">        return (left + right)/2</div><div class="line"></div><div class="line">    leftThird = (2*left + right)/3</div><div class="line">    rightThird = (left + 2*right)/3</div><div class="line"></div><div class="line">    if f(leftThird) &lt; f(rightThird):</div><div class="line">        return ternarySearch(f, leftThird, right, absolutePrecision) </div><div class="line">    else:</div><div class="line">        return ternarySearch(f, left, rightThird, absolutePrecision)</div></pre></td></tr></table></figure>
<h5 id="Iterative-algorithm"><a href="#Iterative-algorithm" class="headerlink" title="Iterative algorithm"></a>Iterative algorithm</h5><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div></pre></td><td class="code"><pre><div class="line">def ternarySearch(f, left, right, absolutePrecision):</div><div class="line">    &quot;&quot;&quot;</div><div class="line">    Find maximum of unimodal function f() within [left, right]</div><div class="line">    To find the minimum, reverse the if/else statement or reverse the comparison.</div><div class="line">    &quot;&quot;&quot;</div><div class="line">    while True:</div><div class="line">        #left and right are the current bounds; the maximum is between them</div><div class="line">        if abs(right - left) &lt; absolutePrecision:</div><div class="line">            return (left + right)/2</div><div class="line"></div><div class="line">        leftThird = left + (right - left)/3</div><div class="line">        rightThird = right - (right - left)/3</div><div class="line"></div><div class="line">        if f(leftThird) &lt; f(rightThird):</div><div class="line">            left = leftThird</div><div class="line">        else:</div><div class="line">            right = rightThird</div></pre></td></tr></table></figure>
        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/11/02/alg_3/" data-id="cj9i7rg040000vcrd3hnlv89x" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-alg_pack" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/11/02/alg_pack/">背包问题</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/11/02/alg_pack/">
            <time datetime="2017-11-02T07:24:39.198Z" itemprop="datePublished">2017-11-02</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/算法和数据结构/">算法和数据结构</a>
    </div>

                        
                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <ul>
<li>01背包（ZeroOnePack）<br>有<code>N</code>件物品和一个容量为<code>W</code>的背包。（<strong>每种物品均只有一件</strong>）第<code>i</code>件物品的重量是<code>w[i]</code>，价值是<code>v[i]</code>。求解将哪些物品装入背包可使价值总和最大。</li>
<li>完全背包(CompletePack)<br>有<code>N</code>种物品和一个容量为<code>W</code>的背包，<strong>每种物品都有无限件可用</strong>。第<code>i</code>种物品的费用是<code>w[i]</code>，价值是<code>v[i]</code>。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。</li>
<li>多重背包(MultiplePack)<br>有<code>N</code>种物品和一个容量为<code>W</code>背包。<strong>第<code>i</code>种物品最多有<code>n[i]</code>件可用</strong>，每件费用是<code>w[i]</code>，价值是<code>v[i]</code>。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。</li>
</ul>
<h1 id="一要注意每个循环的取值范围"><a href="#一要注意每个循环的取值范围" class="headerlink" title="一要注意每个循环的取值范围"></a>一要注意每个循环的<strong>取值范围</strong></h1><h1 id="二要注意每个循环的循环方向"><a href="#二要注意每个循环的循环方向" class="headerlink" title="二要注意每个循环的循环方向"></a>二要注意每个循环的<strong>循环方向</strong></h1><h1 id="01背包"><a href="#01背包" class="headerlink" title="01背包"></a>01背包</h1><p>递推式：<code>dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])</code></p>
<ul>
<li><p>二维数组，正向，时间<code>O(NW)</code>,空间<code>O(NW)</code></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div></pre></td><td class="code"><pre><div class="line"></div><div class="line">for (int j = 0; j &lt;= W; ++j) &#123;</div><div class="line">    dp[0][j] = 0;</div><div class="line">&#125;</div><div class="line">for (int i = 1; i &lt; N; ++i) &#123;</div><div class="line">    for (int j = 0; j &lt;= W; ++j) &#123;</div><div class="line">        if (j &lt; w[i])</div><div class="line">            dp[i][j] = dp[i - 1][j];</div><div class="line">        else</div><div class="line">            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])</div><div class="line">        &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
<li><p>优化空间复杂度——一维数组，外循环正向，内循环逆向，时间<code>O(NW)</code>,空间<code>O(W)</code></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line"></div><div class="line">for (int i = 0; i &lt; N; ++i) &#123;</div><div class="line">    for (int j = W; j &gt;= w[i]; --j) &#123;</div><div class="line">        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
</ul>
<p><strong><em>Note:</em></strong> 为啥是逆向？<br>要保证在推<code>dp[i][j]</code>时，能够取用<code>dp[i - 1][j]</code>和<code>dp[i - 1][j - w[i]]</code>,看图，只有当j<code>从右向左</code>更新的时候，更新到<code>dp[j]</code>时才能取用到<strong>原来的</strong><code>dp[j]</code>和<code>dp[j-w[i]]</code>.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line">        j-w[i]     j    </div><div class="line">i-1      ●         ●</div><div class="line">i                  ☆</div></pre></td></tr></table></figure>
<p>☆表示要求的状态，●表示求☆状态需要的状态</p>
<h1 id="完全背包"><a href="#完全背包" class="headerlink" title="完全背包"></a>完全背包</h1><p>这个问题有三种优化方式，（参考背包九讲）现在只选第三种<code>O(NW)</code>的算法<br>其实就是对第i件物品放入多少进行讨论，分两种就好了，一件都不放！放一件以上！于是：<br>递推式：<code>dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+w[i])，内外循环都是正向！</code><br>其中，</p>
<ul>
<li>dp[i-1][j]——一件都没放</li>
<li>dp[i][j-w[i]]+v[i]——至少放了一件<br>一维数组代码如下，<strong>它跟01背包问题的代码只有内循环方向相反而已！！</strong><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line">        j-w[i]     j    </div><div class="line">i-1                ●</div><div class="line">i         ●        ☆</div></pre></td></tr></table></figure>
</li>
</ul>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line">for (int i = 0; i &lt; N; ++i) &#123;</div><div class="line">    for (int j = w[i]; j &lt;= W; ++j) &#123;</div><div class="line">        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p><strong><em>Note:</em></strong> 关于滚动降维后的循环方向问题，看递推式，像上面一样画图表示后就一目了然！</p>
<h1 id="多重背包"><a href="#多重背包" class="headerlink" title="多重背包"></a>多重背包</h1><p>递推式见“背包九讲”<br>多重背包好像较多用于判断可行性（POJ 1742）</p>

        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/11/02/alg_pack/" data-id="cj9i63i9000009crd5cu6rhqd" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-alg_1" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/11/02/alg_1/">常用的几个code snippet</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/11/02/alg_1/">
            <time datetime="2017-11-02T07:21:39.404Z" itemprop="datePublished">2017-11-02</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/算法和数据结构/">算法和数据结构</a>
    </div>

                        
                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h1 id="进制转换"><a href="#进制转换" class="headerlink" title="进制转换"></a>进制转换</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//将x转为n进制</span></div><div class="line"><span class="function"><span class="keyword">static</span> String <span class="title">convert</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">        StringBuilder sb = <span class="keyword">new</span> StringBuilder();</div><div class="line">        <span class="keyword">while</span> (x &gt; <span class="number">0</span>) &#123;</div><div class="line">            sb.insert(<span class="number">0</span>, x % n);</div><div class="line">            x /= n;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> sb.toString();</div><div class="line">    &#125;</div></pre></td></tr></table></figure>
<h1 id="求素数（求素数-md）"><a href="#求素数（求素数-md）" class="headerlink" title="求素数（求素数.md）"></a>求素数（求素数.md）</h1><h1 id="计算两个整数a-b的最大公约数（欧几里德算法）"><a href="#计算两个整数a-b的最大公约数（欧几里德算法）" class="headerlink" title="计算两个整数a,b的最大公约数（欧几里德算法）"></a>计算两个整数a,b的最大公约数（欧几里德算法）</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">gcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</div><div class="line">  <span class="keyword">if</span>(b==<span class="number">0</span>)<span class="keyword">return</span> a;</div><div class="line">  <span class="keyword">return</span> gcd(b,a%b);</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h1 id="在已知a-b求解一组x，y使得ax-by-gcd-a-b-d-扩展欧几里德算法"><a href="#在已知a-b求解一组x，y使得ax-by-gcd-a-b-d-扩展欧几里德算法" class="headerlink" title="在已知a, b求解一组x，y使得ax+by = gcd(a, b) =d(扩展欧几里德算法)"></a>在已知a, b求解一组x，y使得<code>ax+by = gcd(a, b) =d</code>(扩展欧几里德算法)</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">exGcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b,<span class="keyword">int</span> &amp;x,<span class="keyword">int</span> &amp;y)</span></span></div><div class="line">&#123;</div><div class="line">    <span class="keyword">if</span>(b==<span class="number">0</span>)</div><div class="line">    &#123;</div><div class="line">        x=<span class="number">1</span>;y=<span class="number">0</span>;</div><div class="line">        <span class="keyword">return</span> a;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> r=exGcd(b,a%b,x,y);</div><div class="line">    <span class="keyword">int</span> t=x;x=y;y=t-a/b*y;</div><div class="line">    <span class="keyword">return</span> r;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<ol>
<li><p>试除法</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line">int is_prime(int n)</div><div class="line">  &#123;  int i;</div><div class="line">      if (n&lt;=1)  return 0;    //n不是素数，返回零</div><div class="line">      for(i=2; i*i&lt;=n; i++)    //for(int i = 2; i &lt;= sqrt(n); ++i)</div><div class="line">          &#123; </div><div class="line">            if( n%i==0 ) return 0;  //判断n能否被i整除</div><div class="line">          &#125;</div><div class="line">      return 1;</div><div class="line">  &#125;</div></pre></td></tr></table></figure>
</li>
<li><p>筛法(Eratosthenes)</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line">//筛选法求1000以内素数（删除所有素数的倍数）</div><div class="line">    vector&lt;int&gt; v(1000,1);</div><div class="line">    for(int i=2;i&lt;1000;++i)&#123;</div><div class="line">        for(int j=2;i*j&lt;1000;++j)&#123;</div><div class="line">            if(v[i])&#123;</div><div class="line">                v[i*j]=0;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div></pre></td></tr></table></figure>
</li>
</ol>
<h1 id="快速幂运算"><a href="#快速幂运算" class="headerlink" title="快速幂运算"></a>快速幂运算</h1><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div></pre></td><td class="code"><pre><div class="line">typedef long long ll;</div><div class="line">ll mod_pow(ll x, ll n, ll mod) &#123;</div><div class="line">ll res = 1;</div><div class="line">while (n) &#123;</div><div class="line">if (n &amp; 1)res = res * x % mod;</div><div class="line">x = x * x % mod;</div><div class="line">n &gt;&gt; 1;</div><div class="line">&#125;</div><div class="line">return res;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h1 id="统计后面小于自己的个数"><a href="#统计后面小于自己的个数" class="headerlink" title="统计后面小于自己的个数"></a>统计后面小于自己的个数</h1><p>也就是 315. Count of Smaller Numbers After Self<br>此题还能用线段树解，但是代码太多，直接二分法吧。<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div></pre></td><td class="code"><pre><div class="line">public List&lt;Integer&gt; countSmaller(int[] nums) &#123;</div><div class="line">        Integer[] ans = new Integer[nums.length];</div><div class="line">        List&lt;Integer&gt; sorted = new ArrayList&lt;Integer&gt;();</div><div class="line">        for (int i = nums.length - 1; i &gt;= 0; i--) &#123;</div><div class="line">            int index = findIndex(sorted, nums[i]);</div><div class="line">            ans[i] = index;</div><div class="line">            sorted.add(index, nums[i]);</div><div class="line">        &#125;</div><div class="line">        return Arrays.asList(ans);</div><div class="line">    &#125;</div><div class="line">    private int findIndex(List&lt;Integer&gt; sorted, int target) &#123;</div><div class="line">        if (sorted.size() == 0) return 0;</div><div class="line">        int start = 0;</div><div class="line">        int end = sorted.size() - 1;</div><div class="line">        if (sorted.get(end) &lt; target) return end + 1;</div><div class="line">        if (sorted.get(start) &gt;= target) return 0;</div><div class="line">        while (start + 1 &lt; end) &#123;</div><div class="line">            int mid = start + (end - start) / 2;</div><div class="line">            if (sorted.get(mid) &lt; target) &#123;</div><div class="line">                start = mid + 1;</div><div class="line">            &#125; else &#123;</div><div class="line">                end = mid;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        if (sorted.get(start) &gt;= target) return start;</div><div class="line">        return end;</div><div class="line">    &#125;</div></pre></td></tr></table></figure></p>
<h1 id="最长递增序列（LIS"><a href="#最长递增序列（LIS" class="headerlink" title="最长递增序列（LIS)"></a>最长递增序列（LIS)</h1><ol>
<li>（不采用）基础解法，O(n^2), TLE<br>dp[i]=以ai为末尾的最长上升子序列的长度<br>转移式：`dp[i]=max(dp[i],dp[j]+1) j&lt;i</li>
<li>优化解法，O(n*logn)<br>dp[i]=长度为i+1的上升子序列中末尾元素的最小值</li>
</ol>
<p><strong>Java8</strong><br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div></pre></td><td class="code"><pre><div class="line">public int lengthOfLIS(int[] nums) &#123;</div><div class="line">    if(nums==null || nums.length==0)</div><div class="line">        return 0;</div><div class="line"> </div><div class="line">    ArrayList&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;(); </div><div class="line"> </div><div class="line">    for(int num: nums)&#123;</div><div class="line">        if(list.size()==0 || num&gt;list.get(list.size()-1))&#123;</div><div class="line">            list.add(num);</div><div class="line">        &#125;else&#123;</div><div class="line">            int i=0; </div><div class="line">            int j=list.size()-1;</div><div class="line"> </div><div class="line">            while(i&lt;j)&#123;</div><div class="line">                int mid = (i+j)/2;</div><div class="line">                if(list.get(mid) &lt; num)&#123;</div><div class="line">                    i=mid+1;</div><div class="line">                &#125;else&#123;</div><div class="line">                    j=mid;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line"> </div><div class="line">            list.set(j, num);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"> </div><div class="line">    return list.size();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p><strong>C++</strong><br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line">int lengthOfLIS(vector&lt;int&gt;&amp; nums) &#123;</div><div class="line">    vector&lt;int&gt; ans;</div><div class="line">    for (int a : nums)</div><div class="line">        if (ans.size() == 0 || a &gt; ans.back()) ans.push_back(a);</div><div class="line">        else *lower_bound(ans.begin(), ans.end(), a) = a;</div><div class="line">    return ans.size();</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<h1 id="最长公共子序列-LCS"><a href="#最长公共子序列-LCS" class="headerlink" title="最长公共子序列(LCS)"></a>最长公共子序列(LCS)</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestCommonSubsequence</span><span class="params">(String A, String B)</span> </span>&#123;</div><div class="line">      <span class="keyword">int</span> n = A.length();</div><div class="line">      <span class="keyword">int</span> m = B.length();</div><div class="line">      <span class="keyword">int</span> f[][] = <span class="keyword">new</span> <span class="keyword">int</span>[n + <span class="number">1</span>][m + <span class="number">1</span>];</div><div class="line">      <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)&#123;</div><div class="line">          <span class="keyword">for</span>(<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= m; j++)&#123;</div><div class="line">              f[i][j] = Math.max(f[i - <span class="number">1</span>][j], f[i][j - <span class="number">1</span>]);</div><div class="line">              <span class="keyword">if</span>(A.charAt(i - <span class="number">1</span>) == B.charAt(j - <span class="number">1</span>))</div><div class="line">                  f[i][j] = f[i - <span class="number">1</span>][j - <span class="number">1</span>] + <span class="number">1</span>;</div><div class="line">          &#125;</div><div class="line">      &#125;</div><div class="line">      <span class="keyword">return</span> f[n][m];</div><div class="line">  &#125;</div></pre></td></tr></table></figure>

        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/11/02/alg_1/" data-id="cj9i5kqgz0000ysrdp6thcvpk" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-image_warp_1" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/11/02/image_warp_1/">人脸变形常用方法</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/11/02/image_warp_1/">
            <time datetime="2017-11-02T05:53:11.636Z" itemprop="datePublished">2017-11-02</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/图像处理/">图像处理</a>
    </div>

                        
                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <p>   实验室接的项目，客户是某大型婚纱摄影公司。要求把刚拍好的婚纱照尽量美化，节省百分之八十的美工工作。我负责人脸变形部分，调整脸型和五官。<br>调研一番后，发现很多APP都已经实现了实时瘦脸和大眼两个功能，用的算法就两种，调整形状用图像局部扭曲算法，放大用图像局部放大算法。</p>
<h1 id="图像局部扭曲算法"><a href="#图像局部扭曲算法" class="headerlink" title="图像局部扭曲算法"></a>图像局部扭曲算法</h1><p>   图像局部扭曲其实就是PS中的“液化”效果，又称为前倾变形。<br>   <img src="http://oys1i1ypm.bkt.clouddn.com/yehua.png?imageMogr/v2/thumbnail/500x500" alt="液化"><br>   这种变形算法我参考了<a href="http://blog.csdn.net/xiaotie1005/article/details/48949151" target="_blank" rel="external">这篇博客</a><br>   但是其中只给了简要的步骤，并没有讲明具体的插值办法，所以自己用双线性插值法写了个完整的算法，主要插值代码如下：</p>
   <figure class="highlight matlab"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div></pre></td><td class="code"><pre><div class="line">  <span class="keyword">for</span> <span class="built_in">j</span> = Top : Bottom</div><div class="line">   <span class="keyword">for</span> <span class="built_in">i</span> = Left : Right</div><div class="line">       dy = <span class="built_in">j</span> - Cy;</div><div class="line">       dx = <span class="built_in">i</span> - Cx;</div><div class="line">       PC2 = dx * dx + dy * dy;   </div><div class="line">       <span class="keyword">if</span> PC2 &lt;= r2</div><div class="line">           k=(r2-PC2)/(r2-PC2+MC2);</div><div class="line">           k2=k*k;</div><div class="line">           x=<span class="built_in">i</span>-k2*MCx;</div><div class="line">           y=<span class="built_in">j</span>-k2*MCy;</div><div class="line">     </div><div class="line">           x=max(x,<span class="number">1</span>);</div><div class="line">           x=min(x,w<span class="number">-1</span>);</div><div class="line">           y=max(y,<span class="number">1</span>);</div><div class="line">           y=min(y,h<span class="number">-1</span>);  </div><div class="line">           </div><div class="line">           x1=<span class="built_in">floor</span>(x);</div><div class="line">           x2=x1+<span class="number">1</span>;</div><div class="line">           y1=<span class="built_in">floor</span>(y);</div><div class="line">           y2=y1+<span class="number">1</span>;</div><div class="line">           </div><div class="line">           tt1=(x2-x)*J(y1,x1,:)+(x-x1)*J(y1,x2,:);</div><div class="line">           tt2=(x2-x)*J(y2,x1,:)+(x-x1)*J(y2,x2,:);            </div><div class="line">           tt=(y2-y)*tt1+(y-y1)*tt2;            </div><div class="line">           J(<span class="built_in">j</span>,<span class="built_in">i</span>,:)=tt;</div><div class="line"></div><div class="line">       <span class="keyword">end</span>  </div><div class="line">   <span class="keyword">end</span></div><div class="line"><span class="keyword">end</span></div></pre></td></tr></table></figure>
<h1 id="图像局部放大算法"><a href="#图像局部放大算法" class="headerlink" title="图像局部放大算法"></a>图像局部放大算法</h1>
        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/11/02/image_warp_1/" data-id="cj9i3wh9w000id8rdfjtyutr1" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-jzoffer_18" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/08/18/jzoffer_18/">二叉搜索树的后序遍历序列</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/08/18/jzoffer_18/">
            <time datetime="2017-08-18T12:33:33.030Z" itemprop="datePublished">2017-08-18</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/剑指/">剑指</a>
    </div>

                        
    <div class="article-tag">
        <i class="fa fa-tag"></i>
        <a class="tag-link" href="/tags/TreeNode/">TreeNode</a>, <a class="tag-link" href="/tags/recursion/">recursion</a>
    </div>

                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h1 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h1><p>输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。</p>
<h1 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h1><p>参考牛客网答案<br>BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。</p>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">VerifySquenceOfBST</span><span class="params">(<span class="keyword">int</span> [] sequence)</span> </span>&#123;</div><div class="line">            <span class="keyword">if</span>(sequence.length==<span class="number">0</span>)<span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">            <span class="keyword">return</span>  check(sequence,<span class="number">0</span>,sequence.length-<span class="number">1</span>);</div><div class="line">            </div><div class="line">        &#125;</div><div class="line">        </div><div class="line">        <span class="function"><span class="keyword">boolean</span> <span class="title">check</span><span class="params">(<span class="keyword">int</span> [] s,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span>&#123;</div><div class="line">            <span class="keyword">if</span>(l&gt;=r)<span class="keyword">return</span> <span class="keyword">true</span>;</div><div class="line">            <span class="keyword">int</span> i=r;</div><div class="line">            <span class="keyword">while</span>(i&gt;l &amp;&amp; s[i-<span class="number">1</span>]&gt;s[r])i--;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j=i-<span class="number">1</span>;j&gt;=l;j--)&#123;</div><div class="line">                <span class="keyword">if</span>(s[j]&gt;s[r])</div><div class="line">                    <span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">return</span> check(s,l,i-<span class="number">1</span>) &amp;&amp; check(s,i,r-<span class="number">1</span>);</div><div class="line">        &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/08/18/jzoffer_18/" data-id="cj9i3whao0015d8rd63367y7t" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-jzoffer_17" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/08/18/jzoffer_17/">二叉树的镜像</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/08/18/jzoffer_17/">
            <time datetime="2017-08-18T12:25:52.553Z" itemprop="datePublished">2017-08-18</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/剑指/">剑指</a>
    </div>

                        
    <div class="article-tag">
        <i class="fa fa-tag"></i>
        <a class="tag-link" href="/tags/TreeNode/">TreeNode</a>, <a class="tag-link" href="/tags/recursion/">recursion</a>
    </div>

                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h1 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h1><p>操作给定的二叉树，将其变换为源二叉树的镜像。</p>
<h1 id="输入描述"><a href="#输入描述" class="headerlink" title="输入描述:"></a>输入描述:</h1><p>二叉树的镜像定义：源二叉树<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div></pre></td><td class="code"><pre><div class="line">    <span class="number">8</span></div><div class="line">   /  \</div><div class="line">  <span class="number">6</span>   <span class="number">10</span></div><div class="line"> / \  / \</div><div class="line"><span class="number">5</span>  <span class="number">7</span> <span class="number">9</span> <span class="number">11</span></div><div class="line">镜像二叉树</div><div class="line">    <span class="number">8</span></div><div class="line">   /  \</div><div class="line">  <span class="number">10</span>   <span class="number">6</span></div><div class="line"> / \  / \</div><div class="line"><span class="number">11</span> <span class="number">9</span> <span class="number">7</span>  <span class="number">5</span></div></pre></td></tr></table></figure></p>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">Mirror</span><span class="params">(TreeNode root)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span>(root==<span class="keyword">null</span>)<span class="keyword">return</span>;</div><div class="line">        TreeNode tmp=root.left;</div><div class="line">        root.left=root.right;</div><div class="line">        root.right=tmp;</div><div class="line">        Mirror(root.left);</div><div class="line">        Mirror(root.right);</div><div class="line">        </div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/08/18/jzoffer_17/" data-id="cj9i3whaq0018d8rd4vuz9sk4" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-jzoffer_16" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/08/18/jzoffer_16/">HasSubtree</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/08/18/jzoffer_16/">
            <time datetime="2017-08-18T12:24:16.644Z" itemprop="datePublished">2017-08-18</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/剑指/">剑指</a>
    </div>

                        
    <div class="article-tag">
        <i class="fa fa-tag"></i>
        <a class="tag-link" href="/tags/TreeNode/">TreeNode</a>, <a class="tag-link" href="/tags/recursion/">recursion</a>
    </div>

                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h1 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h1><p>输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）</p>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">HasSubtree</span><span class="params">(TreeNode root1,TreeNode root2)</span> </span>&#123;</div><div class="line">            <span class="keyword">if</span>(root1==<span class="keyword">null</span> || root2==<span class="keyword">null</span>)<span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">            <span class="keyword">return</span> isEqual(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);</div><div class="line">            </div><div class="line">        &#125;</div><div class="line">        </div><div class="line">        </div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEqual</span><span class="params">(TreeNode r1,TreeNode r2)</span></span>&#123;</div><div class="line">            <span class="keyword">if</span>(r2==<span class="keyword">null</span>)<span class="keyword">return</span> <span class="keyword">true</span>;</div><div class="line">            <span class="keyword">if</span>(r1==<span class="keyword">null</span>)<span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">            <span class="keyword">return</span> r1.val==r2.val &amp;&amp; isEqual(r1.left,r2.left) &amp;&amp; isEqual(r1.right,r2.right);</div><div class="line">        &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/08/18/jzoffer_16/" data-id="cj9i3whai0010d8rdopw8zogl" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-honor_2" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/08/02/honor_2/">花花使用总结</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/08/02/honor_2/">
            <time datetime="2017-08-02T07:44:58.289Z" itemprop="datePublished">2017-08-02</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/农药/">农药</a>
    </div>

                        
    <div class="article-tag">
        <i class="fa fa-tag"></i>
        <a class="tag-link" href="/tags/花木兰/">花木兰</a>
    </div>

                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h3 id="上单"><a href="#上单" class="headerlink" title="上单"></a>上单</h3><ol>
<li>反红<br>开局不点技能，蹲草丛，36’左右去敌红，如果顺利，点2技能扔红，不顺利一技能逃跑。</li>
<li>gank<br>不要急着收小兵，利用地方兵线作为跳板， 轻剑1技能贴近，平A加2技能打出沉默，逃跑的话，再1技能追上，切大招推人</li>
</ol>
<h3 id="打野"><a href="#打野" class="headerlink" title="打野"></a>打野</h3><p>我发现打野gank成功率比上单高</p>
<h3 id="重剑连招"><a href="#重剑连招" class="headerlink" title="重剑连招"></a>重剑连招</h3><p><code>轻剑3转重剑——A——2——1——A——1</code></p>

        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/08/02/honor_2/" data-id="cj9i3wh9o0009d8rda22sp6w8" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-jzoffer_15" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/07/21/jzoffer_15/">反转链表</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/07/21/jzoffer_15/">
            <time datetime="2017-07-21T08:23:05.883Z" itemprop="datePublished">2017-07-21</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/剑指/">剑指</a>
    </div>

                        
    <div class="article-tag">
        <i class="fa fa-tag"></i>
        <a class="tag-link" href="/tags/list/">list</a>, <a class="tag-link" href="/tags/reverse/">reverse</a>
    </div>

                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h1 id="Recursion"><a href="#Recursion" class="headerlink" title="Recursion"></a>Recursion</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> ListNode <span class="title">ReverseList</span><span class="params">(ListNode head)</span> </span>&#123;</div><div class="line">		<span class="keyword">if</span>(head==<span class="keyword">null</span> || head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</div><div class="line">        ListNode pre=ReverseList(head.next);</div><div class="line">        head.next.next=head;</div><div class="line">        head.next=<span class="keyword">null</span>;</div><div class="line">        <span class="keyword">return</span> pre;</div><div class="line">        </div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h1 id="Iteration"><a href="#Iteration" class="headerlink" title="Iteration"></a>Iteration</h1><p><code>while</code>里面就做一件事，把所有向右的箭头全部变成向左<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> ListNode <span class="title">ReverseList</span><span class="params">(ListNode head)</span> </span>&#123;</div><div class="line">		<span class="keyword">if</span>(head==<span class="keyword">null</span> || head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</div><div class="line">        </div><div class="line">        ListNode rHead=<span class="keyword">null</span>,cur=head,pre=<span class="keyword">null</span>;</div><div class="line">        <span class="keyword">while</span>(cur.next!=<span class="keyword">null</span>)&#123;</div><div class="line">            ListNode tmp=cur.next;</div><div class="line">            cur.next=pre;</div><div class="line">            pre=cur;</div><div class="line">            cur=tmp;</div><div class="line">            </div><div class="line">        &#125;</div><div class="line">        rHead=cur;</div><div class="line">        cur.next=pre;</div><div class="line">        <span class="keyword">return</span> rHead;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line">`</div></pre></td></tr></table></figure></p>

        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/07/21/jzoffer_15/" data-id="cj9i3whac000vd8rdv0m4t3cl" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <article id="post-jzoffer_14" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
            <header class="article-header">
                
    
        <h1 itemprop="name">
            <a class="article-title" href="/2017/07/21/jzoffer_14/">链表中倒数第k个结点</a>
        </h1>
    

                
                    <div class="article-meta">
                        
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2017/07/21/jzoffer_14/">
            <time datetime="2017-07-21T06:59:53.682Z" itemprop="datePublished">2017-07-21</time>
        </a>
    </div>


                        
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/剑指/">剑指</a>
    </div>

                        
    <div class="article-tag">
        <i class="fa fa-tag"></i>
        <a class="tag-link" href="/tags/list/">list</a>, <a class="tag-link" href="/tags/two-pointers/">two pointers</a>
    </div>

                    </div>
                
            </header>
        
        
        <div class="article-entry" itemprop="articleBody">
        
            
            <h1 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h1><p>输入一个链表，输出该链表中倒数第k个结点。</p>
<h1 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h1><p>双指针，fast,slow</p>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> ListNode <span class="title">FindKthToTail</span><span class="params">(ListNode head,<span class="keyword">int</span> k)</span> </span>&#123;</div><div class="line">        ListNode fast=head,slow=head;</div><div class="line">        </div><div class="line">        <span class="keyword">while</span>(k&gt;<span class="number">0</span> &amp;&amp; fast!=<span class="keyword">null</span>)&#123;</div><div class="line">            fast=fast.next;</div><div class="line">            k--;</div><div class="line">        &#125;</div><div class="line">        </div><div class="line">        <span class="keyword">if</span>(k&gt;<span class="number">0</span>)<span class="keyword">return</span> <span class="keyword">null</span>;</div><div class="line">        </div><div class="line">       <span class="keyword">while</span>(fast!=<span class="keyword">null</span>)&#123;</div><div class="line">           fast=fast.next;</div><div class="line">           slow=slow.next;</div><div class="line">       &#125;</div><div class="line">        <span class="keyword">return</span> slow;</div><div class="line">      </div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yoursite.com/2017/07/21/jzoffer_14/" data-id="cj9i3whaf000xd8rddaff518f" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    

        </footer>
    </div>
    
</article>



    <nav id="page-nav">
        <span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="page-number" href="/page/3/">3</a><a class="extend next" rel="next" href="/page/2/">下一页 &raquo;</a>
    </nav>
</section>
            
                
<aside id="sidebar">
   
        
    <div class="widget-wrap">
        <h3 class="widget-title">最新文章</h3>
        <div class="widget">
            <ul id="recent-post" class="no-thumbnail">
                
                    <li>
                        
                        <div class="item-inner">
                            <p class="item-category"><a class="article-category-link" href="/categories/算法和数据结构/">算法和数据结构</a></p>
                            <p class="item-title"><a href="/2017/11/02/alg_3/" class="title">Ternary search（三元搜索）</a></p>
                            <p class="item-date"><time datetime="2017-11-02T08:25:05.694Z" itemprop="datePublished">2017-11-02</time></p>
                        </div>
                    </li>
                
                    <li>
                        
                        <div class="item-inner">
                            <p class="item-category"><a class="article-category-link" href="/categories/算法和数据结构/">算法和数据结构</a></p>
                            <p class="item-title"><a href="/2017/11/02/alg_pack/" class="title">背包问题</a></p>
                            <p class="item-date"><time datetime="2017-11-02T07:24:39.198Z" itemprop="datePublished">2017-11-02</time></p>
                        </div>
                    </li>
                
                    <li>
                        
                        <div class="item-inner">
                            <p class="item-category"><a class="article-category-link" href="/categories/算法和数据结构/">算法和数据结构</a></p>
                            <p class="item-title"><a href="/2017/11/02/alg_1/" class="title">常用的几个code snippet</a></p>
                            <p class="item-date"><time datetime="2017-11-02T07:21:39.404Z" itemprop="datePublished">2017-11-02</time></p>
                        </div>
                    </li>
                
                    <li>
                        
                        <div class="item-inner">
                            <p class="item-category"><a class="article-category-link" href="/categories/图像处理/">图像处理</a></p>
                            <p class="item-title"><a href="/2017/11/02/image_warp_1/" class="title">人脸变形常用方法</a></p>
                            <p class="item-date"><time datetime="2017-11-02T05:53:11.636Z" itemprop="datePublished">2017-11-02</time></p>
                        </div>
                    </li>
                
                    <li>
                        
                        <div class="item-inner">
                            <p class="item-category"><a class="article-category-link" href="/categories/剑指/">剑指</a></p>
                            <p class="item-title"><a href="/2017/08/18/jzoffer_18/" class="title">二叉搜索树的后序遍历序列</a></p>
                            <p class="item-date"><time datetime="2017-08-18T12:33:33.030Z" itemprop="datePublished">2017-08-18</time></p>
                        </div>
                    </li>
                
            </ul>
        </div>
    </div>

    
        
    <div class="widget-wrap">
        <h3 class="widget-title">分类</h3>
        <div class="widget">
            <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/IOS/">IOS</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Kickstart/">Kickstart</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/LeetCode/">LeetCode</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/POJ/">POJ</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/农药/">农药</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/剑指/">剑指</a><span class="category-list-count">18</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/图像处理/">图像处理</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/图像理解/">图像理解</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/广播剧/">广播剧</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/算法和数据结构/">算法和数据结构</a><span class="category-list-count">3</span></li></ul>
        </div>
    </div>

    
        
    <div class="widget-wrap">
        <h3 class="widget-title">归档</h3>
        <div class="widget">
            <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/11/">十一月 2017</a><span class="archive-list-count">4</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/08/">八月 2017</a><span class="archive-list-count">4</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/07/">七月 2017</a><span class="archive-list-count">22</span></li></ul>
        </div>
    </div>

    
        
    <div class="widget-wrap">
        <h3 class="widget-title">标签</h3>
        <div class="widget">
            <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/IOS/">IOS</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/TreeNode/">TreeNode</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/array/">array</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/binary-search/">binary search</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/binary-tree/">binary tree</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/bit-manipulation/">bit manipulation</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/dp/">dp</a><span class="tag-list-count">6</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/list/">list</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/queue/">queue</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/recursion/">recursion</a><span class="tag-list-count">4</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/reverse/">reverse</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/rotate-array/">rotate array</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/search/">search</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/stack/">stack</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/string/">string</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tree/">tree</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/two-pointers/">two pointers</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/个人YY/">个人YY</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/二分法/">二分法</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/最大化最小值/">最大化最小值</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/花木兰/">花木兰</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/贪心/">贪心</a><span class="tag-list-count">1</span></li></ul>
        </div>
    </div>

    
        
    <div class="widget-wrap">
        <h3 class="widget-title">标签云</h3>
        <div class="widget tagcloud">
            <a href="/tags/IOS/" style="font-size: 10px;">IOS</a> <a href="/tags/TreeNode/" style="font-size: 15px;">TreeNode</a> <a href="/tags/array/" style="font-size: 10px;">array</a> <a href="/tags/binary-search/" style="font-size: 10px;">binary search</a> <a href="/tags/binary-tree/" style="font-size: 10px;">binary tree</a> <a href="/tags/bit-manipulation/" style="font-size: 12.5px;">bit manipulation</a> <a href="/tags/dp/" style="font-size: 20px;">dp</a> <a href="/tags/list/" style="font-size: 15px;">list</a> <a href="/tags/queue/" style="font-size: 10px;">queue</a> <a href="/tags/recursion/" style="font-size: 17.5px;">recursion</a> <a href="/tags/reverse/" style="font-size: 10px;">reverse</a> <a href="/tags/rotate-array/" style="font-size: 10px;">rotate array</a> <a href="/tags/search/" style="font-size: 12.5px;">search</a> <a href="/tags/stack/" style="font-size: 10px;">stack</a> <a href="/tags/string/" style="font-size: 10px;">string</a> <a href="/tags/tree/" style="font-size: 10px;">tree</a> <a href="/tags/two-pointers/" style="font-size: 10px;">two pointers</a> <a href="/tags/个人YY/" style="font-size: 10px;">个人YY</a> <a href="/tags/二分法/" style="font-size: 10px;">二分法</a> <a href="/tags/最大化最小值/" style="font-size: 10px;">最大化最小值</a> <a href="/tags/花木兰/" style="font-size: 10px;">花木兰</a> <a href="/tags/贪心/" style="font-size: 10px;">贪心</a>
        </div>
    </div>

    
        
    <div class="widget-wrap widget-list">
        <h3 class="widget-title">链接</h3>
        <div class="widget">
            <ul>
                
                    <li>
                        <a href="http://hexo.io">Hexo</a>
                    </li>
                
            </ul>
        </div>
    </div>


    
    <div id="toTop" class="fa fa-angle-up"></div>
</aside>

            
        </div>
        <footer id="footer">
    <div class="outer">
        <div id="footer-info" class="inner">
            &copy; 2017 Alison<br>
            Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>. Theme by <a href="http://github.com/ppoffice">PPOffice</a>
        </div>
    </div>
</footer>
        
    
	<link rel="stylesheet" href="https://imsun.github.io/gitment/style/default.css">
	<script src="https://imsun.github.io/gitment/dist/gitment.browser.js"></script>
	<script>
		var gitment = new Gitment({
			owner: 'AlphaUMa',
			repo: 'AlphaUma.github.io',
			oauth: {
				client_id: '88686e2c3af6c10c9672',
				client_secret: '26a67ff7928cd7a19ad3eeda713fe2822c2ec2c4',
			},
		})
		gitment.render('commentContainer')
	</script>
	



    
        <script src="/libs/lightgallery/js/lightgallery.min.js"></script>
        <script src="/libs/lightgallery/js/lg-thumbnail.min.js"></script>
        <script src="/libs/lightgallery/js/lg-pager.min.js"></script>
        <script src="/libs/lightgallery/js/lg-autoplay.min.js"></script>
        <script src="/libs/lightgallery/js/lg-fullscreen.min.js"></script>
        <script src="/libs/lightgallery/js/lg-zoom.min.js"></script>
        <script src="/libs/lightgallery/js/lg-hash.min.js"></script>
        <script src="/libs/lightgallery/js/lg-share.min.js"></script>
        <script src="/libs/lightgallery/js/lg-video.min.js"></script>
    
    
        <script src="/libs/justified-gallery/jquery.justifiedGallery.min.js"></script>
    
    



<!-- Custom Scripts -->
<script src="/js/main.js"></script>

    </div>
</body>
</html>